package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC587 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        public int[][] outerTrees(int[][] trees) {

            int n = trees.length;

            if (n <= 3) {
                return trees;
            }

            // 计算几何中心
            int sumX = 0;
            int sumY = 0;
            for (int[] tree : trees) {
                sumX += tree[0];
                sumY += tree[1];
            }

            double centerX = sumX / (double) n;
            double centerY = sumY / (double) n;

            // 根据几何中心，按照角度来排序，形成一圈
            Arrays.sort(trees, (o1, o2) -> {
                double angleO1 = Math.atan2(o1[1] - centerY, o1[0] - centerX);
                double angleO2 = Math.atan2(o2[1] - centerY, o2[0] - centerX);
                if (angleO1 == angleO2) {
                    return 0;
                } else {
                    return angleO1 > angleO2 ? 1 : -1;
                }
            });

            // 找到离几何中心最远的一棵树，这棵树一定是在边缘上面的
            double maxDistance = -1;
            int maxTree = -1;
            for (int i = 0; i < n; i++) {
                int[] tree = trees[i];
                double curDistance = Math.sqrt(Math.pow(tree[0] - centerX, 2) + Math.pow(tree[1] - centerY, 2));
                if (curDistance > maxDistance) {
                    maxDistance = curDistance;
                    maxTree = i;
                }
            }

            // 开始以几何中心为中心点逆时针旋转找边缘上面的树
            Deque<int[]> edgeTrees = new LinkedList<>();
            edgeTrees.push(trees[maxTree]);
            edgeTrees.push(trees[(maxTree + 1) % n]);
            Deque<int[]> prevEdgeTrees = new LinkedList<>();
            prevEdgeTrees.push(trees[maxTree]);
            int cur = (maxTree + 2) % n;
            while (cur != (maxTree + 1) % n) {
                while (!prevEdgeTrees.isEmpty()) {
                    int[] prevTree = prevEdgeTrees.peek();
                    int[] oldTree = edgeTrees.peek();
                    int[] newTree = trees[cur];
                    if (cross(prevTree, oldTree, newTree) < 0) {
                        edgeTrees.pop();
                        prevEdgeTrees.pop();
                    } else {
                        break;
                    }
                }
                if (cur != maxTree) {
                    prevEdgeTrees.push(edgeTrees.peek());
                    edgeTrees.push(trees[cur]);
                }
                cur = (cur + 1) % n;
            }

            int resSize = edgeTrees.size();
            int[][] res = new int[resSize][2];
            for (int i = 0; i < resSize; i++) {
                res[i] = edgeTrees.pop();
            }

            return res;
        }

        // 判断是否是逆时针旋转的函数（自己没想出来怎么写，这里是借鉴题解的）
        public int cross(int[] p, int[] q, int[] r) {
            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
        }
    }

    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC587 an = new LC587();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
